翻訳と辞書 Words near each other ・ Kinetic 9 ・ Kinetic architecture ・ Kinetic art ・ Kinetic Awareness ・ Kinetic bombardment ・ Kinetic capillary electrophoresis ・ Kinetic chain length ・ Kinetic Chemicals ・ Kinetic closest pair ・ Kinetic Concepts ・ Kinetic convex hull ・ Kinetic data structure ・ Kinetic depth effect ・ Kinetic diagram ・ Kinetic diameter ・ Kinetic diameter (data) ・ Kinetic Dynamic Suspension System ・ Kinetic energy ・ Kinetic Energy Interceptor ・ Kinetic energy penetrator ・ Kinetic energy recovery system ・ Kinetic Engineering Limited ・ Kinetic Euclidean minimum spanning tree ・ Kinetic exchange models of markets ・ Kinetic Faith ・ Kinetic family drawing ・ Kinetic Flying ・ Kinetic fractionation ・ Kinetic hanger ・ Kinetic heap Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Kinetic diameter (data) ： ウィキペディア英語版 Kinetic diameter (data) A kinetic diameter data structure is a kinetic data structure which maintains the diameter of a set of moving points. The diameter of a set of moving points is the maximum distance between any pair of points in the set. In the two dimensional case, the kinetic data structure for kinetic convex hull can be used to construct a kinetic data structure for the diameter of a moving point set that is responsive, compact and efficient. ==2D Case== The pair of points with maximum pairwise distance must be one of the pairs of antipodal points of the convex hull of all of the points. Note that two points are antipodal points if they have parallel supporting lines. In the static case, the diameter of a point set can be found by computing the convex hull of the point set, finding all pairs of antipodal points, and then finding the maximum distance between these pairs. This algorithm can be kinetized as follows: Consider the dual of the point set. The points dualize to lines and the convex hull of the points dualizes to the upper and lower envelope of the set of lines. The vertices of the upper convex hull dualize to segments on the upper envelope. The vertices of the lower convex hull dualize to segments on the lower envelope. The range of slopes of the supporting lines of a point on the hull dualize to the x-interval of segment that point dualizes to. When viewed in this dualized fashion the antipodal pairs, are pairs of segments, one from the upper envelope, one from the lower, with overlapping x ranges. Now, the upper and lower envelopes can be viewed as two different x-ordered lists of non overlapping intervals. If these two lists are merged, the antipodal pairs are the overlaps in the merged list. The overlaps in the merged list of x-intervals can be maintained by storing the endpoints of the intervals in a kinetic sorted list. When points swap, the list of antipodal pairs are updated. The upper and lower envelopes can be maintained using the standard data structure for kinetic convex hull. The maximum distance between pairs of antipodal can be maintained with a kinetic tournament. Thus, using kinetic convex hull to maintain the upper and lower envelopes, a kinetic sorted list on these intervals to maintain the antipodal pairs, and a kinetic tournament to maintain the pair of maximum distance apart, the diameter of a moving point set can be maintained. This data structure is responsive, compact and efficient. The data structure uses $O(n)$ space because the kinetic convex hull, sorted list, and tournament data structures all use $O(n)$ space. In all of the data structures, events, inserts, and deletes can be handled in $O(\backslash log^2\; n)$ time, so the data structure are responsive, requiring $O(\backslash log^2\; n)$ per event. The data structure is efficient because the total number of events is $O(n^)$ for all $\backslash epsilon>0$ and the diameter of a point set can change $\backslash Omega(n^2)$ times, even if the points are moving linearly. This data structure is not local because one point may be in many antipodal pairs, and thus appear many times in the kinetic tournament. The existence of a local kinetic data structure for diameter is open. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Kinetic diameter (data)」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.